package com.le.enhance.class3;

import org.junit.Test;

/**
 * Morris遍历 利用Morris遍历实现二叉树的先序，中序，后续遍历，
 * --- 时间复杂度O(N)，额外空间复杂度O(1)
 *  重点:
 *      如果一个结点有左节点,那么该节点会经过二次,额外空间复杂度O(1), 没有额外使用栈
 */
public class Code_01_MorrisTraversal {
    public static class Node {
        public int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    /**
     * 传统遍历方式,利用栈解决, 但是同一个结点经过了三次,有许多无效指针
     * @param head
     */
    public static void process(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.val + "  ");
        process(head.left);
//        System.out.print(head.val + "  ");
        process(head.right);
//        System.out.print(head.val + "  ");
    }

    /**
     * Morris遍历:
     * 1. 如果当前结点cur[无]左结点, cur = cur.right
     * 2. 如果当前结点cur有左结点,找到该左子树上最右结点计为mostRight
     * a. 如果mostRight.right =null,让其指向cur, cur = cur.left
     * b. 如果mostRight.right !=null,让其指向null, cur = cur.right
     *
     * @param head
     */
    public static void morrisIn(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
        System.out.println();
    }

    public static void morrisPre(Node head){
        if (head == null){
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){
                    mostRight.right = cur;
                    System.out.print(cur.val + "  ");
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }else {
                System.out.print(cur.val + "  ");
            }
            cur = cur.right;
        }
        System.out.println();
    }

    @Test
    public void test() {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
//        morrisIn(head);
        morrisPre(head);
        process(head);


    }
}
